Format-Preserving Encryption (FPE) encrypts a plaintext of some specified format into a cipher-text of identical format - for example, encrypting a valid credit-card number into a valid credit-card number. The problem has been known for some time, but it has lacked a fully general and rigorous treatment. The authors provide one, starting off by formally defining FPE and security goals for it. They investigate the natural approach for achieving FPE on complex domains, the "Rank-then-encipher" approach, and explore what it can and cannot do. They describe two flavors of unbalanced Feistel networks that can be used for achieving FPE, and they prove new security results for each.