We describe the smallest quantum error correcting (QEC) code to correct for amplitude-damping (AD) noise, namely, a 3-qubit code that corrects all the single-qubit damping errors. We generalize this construction to a family of codes that correct AD noise up to any fixed order of the damping strength. We underpin the fundamental connection between the structure of our codes and the noise structure, via a relaxed form of the Knill-Laflamme conditions, different from existing formulations of approximate QEC conditions. Although the recovery procedure for this code is non-deterministic, our codes are optimal with respect to overheads and outperform existing codes to tackle AD noise in terms of entanglement fidelity. This formulation of probabilistic QEC further leads us to new family of quantum codes tailored to AD noise and also gives rise to a noise-adapted quantum Hamming bound for AD noise. Finally, we construct a set of universal logical gates for the 3-qubit code, thus providing a potential pathway to fault tolerance via this class of codes.