Cation ordering in ABX3 perovskites is important to structural, physical and chemical properties. Here we report discovery of CaCuFeReO6 with the tetragonal AA′BB′O6 double double perovskite structure that was previously only reported for A′=Mn compositions. CaCuFeReO6 occurs in the same phase field as CaCu3Fe2Re2O12 demonstrating that different A-cation ordered peroskites may be obtained in the same chemical system. CaCuFeReO6 has ferrimagnetic order of Fe, Re and Cu spins below TC=567 K, in contrast to Mn analogues where the Mn spins order separately at much lower temperatures. The magnetoresistance of CaCuFeReO6 displays low-field “butterfly” hysteresis with an unusual change from negative to positive values as field increases. Many more AA′BB′O6 double double perovskites may be accessible for A′=Cu and other divalent transition metals at high pressure, so the presently known phases likely represent only the “tip of the iceberg” for this family.