The axion, first proposed to solve the absence of a neutron electric dipole moment, is also an excellent dark matter candidate. If the axion is composite, it must be bound by a novel strong interaction. Some strongly-coupled models, mathematically intractable until now, are recently discovered to be calculable through a mapping onto 5-dimensional gravity. We propose a series of composite and extra dimensional axion models. A basic 5-dimensional model first incorporates the known forces while keeping the axion consistent with gravitational corrections. More sophisticated extensions address other problems in particle physics unrelated to the axion, providing nontrivial predictions that can be tested experimentally. We further propose a composite model that incorporates both the Higgs boson and the axion. By enlarging the color gauge group, we provide a consistent procedure to raise the axion masses as high as TeV collider energy scales, further motivating experimental searches for axion-like particles.