Spinal codes are a new rateless error correcting code designed to efficiently overcome noise and interference plaguing today's wireless networks. Spinal codes are much faster than existing alternative codes, making it possible to provide increased wireless throughput and coverage with existing radio resources. They also work very well over small message sizes, and over highly variable channel conditions, unlike existing alternatives. They are the first rateless code to provably achieve Shannon capacity over both additive Gaussian noise (AWGN) channels and over bit-flip ("BSC") channels with an efficient encoder and decoder. An FPGA hardware implementation of the encoder and decoder achieves over 10 Mbits/s over wireless channels.