The introduction of DNSSEC and the increasing adoption of IPv6 will tend to generate DNS responses too large for standard DNS-over-UDP transport. This will create pressure for clients to switch to TCP for DNS queries, leading to a significant increase in overhead for DNS servers. Huston has proposed a 'stateless' version of TCP to reduce the server-side load on DNS servers handling DNS queries over TCP. Stateless TCP observes that typical DNS-over-TCP queries may be adequately handled by a simplified TCP connection establishment that reduces the kernel state required per connection. We have implemented our own version of statelessTCP under FreeBSD 9 (FreeBSD's current development branch at the time of writing). This report discusses our selected design and implementation, outlines the limitations of other possible alternatives we chose not to implement, and describes preliminary experimental results showing that DNS-over-stateless TCP uses noticeably less server-side resources than regular DNS-over-TCP.