Circular permutation of fluorescent proteins provides a substrate for the design of molecular sensors. Here we describe a systematic exploration of permutation sites for mCherry and mKate using a tandem fusion template approach. Circular permutants retaining more than 60% (mCherry) and 90% (mKate) brightness of the parent molecules are reported, as well as a quantitative evaluation of the fluorescence from neighboring mutations. Truncations of circular permutants indicated essential N- and C-terminal segments and substantial flexibility in the use of these molecules. Structural evaluation of two cp-mKate variants indicated no major conformational changes from the previously reported wild-type structure, and cis conformation of the chromophores. Four cp-mKates were identified with over 80% of native fluorescence, providing important new building blocks for sensor and complementation experiments.