The use of nonlinear lattices with large betatron tune spreads can increase instability and space charge thresholds due to improved Landau damping. Unfortunately, the majority of nonlinear accelerator lattices turn out to be nonintegrable, producing chaotic motion and a complex network of stable and unstable resonances. Recent advances in finding the integrable nonlinear accelerator lattices have led to a proposal to construct at Fermilab a test accelerator with strong nonlinear focusing which avoids resonances and chaotic particle motion. This presentation will outline the main challenges, theoretical design solutions and construction status of the Integrable Optics Test Accelerator underway at Fermilab.