Carbon nanotubes (CNTs), with their unique electronic properties, are promising materials for building nanoscale circuits. In this paper, we present a new CNT-based FPGA architecture known as FPCNA. We define novel CNT and nanoswitch based components and characterize these components considering nanospecific process variations, including the variation caused by the random mixture of metallic and semiconducting CNTs. To evaluate the architecture, we develop a variation-aware physicaldesign flow which can handle both Gaussian and non-Gaussian random variables using variation-aware placement and routing. When FPCNA is evaluated with this CAD flow, we see a 2.67× performance gain over a baseline CMOS FPGA at the same technology node (at a 95% performance yield). In addition, FPCNA offers a 4.5× footprint reduction compared to the baseline FPGA. These results demonstrate the potential of using CNTs and nanoswitches to build high performance FPGA circuits.