The construction of the stone kremlin in Kolomna began on May 25, 1525, at the initiative of Grand Prince Vasily III and lasted for six years. The kremlin was built outside the wooden wall and was a polygon close to an oval, with a wall perimeter of almost 2 km, which is only 300 m shorter than the walls of the Moscow Kremlin. The thickness of the walls was 3-4.5 m, and their height was 18-21 m. They were faced with brick and had stone filling inside, equipped with loopholes for various types of combat. The walls were topped with battlements, on which shutters for protection were attached. The number of towers changed over different periods, but the kremlin had at least 13 towers and six gates: three 'large' ones, the Pyatnitskiye, Ivanovskiye, and Kosyye, and three 'small' ones, the Malakhovskiye, Georgiyevskiye, and Vodyaniye. The northwestern and northeastern corners of the fortress were protected by the powerful Kolomenskaya and Sviblova towers. The Sviblova tower, the tallest and strongest, controlled the flow of the Moscow River and the road to the Pyatnitskiye gates. Its height reached 34.6 m, and its diameter was 13.8 m. The Kolomenskaya tower, at a height of 34.4 m, controlled the Moscow-Ryazan road and was decorated with decorative machicolations. It is associated with the legend of Marina Mnishek, which is why it is called 'Marinka's'. The main entrance to the kremlin was through the Spasskiye, or Pyatnitskiye gates, which were a three-tiered tower with a watchtower. The Ivanovskiye gates in the southwest of the kremlin resembled the Pyatnitskiye and also had grilles. The Granovitaya tower to the south of the Kolomenskaya tower was five-tiered and hexagonal on the outside. On the eastern side were four-sided towers: Yamskaya, Spasskaya, and Pogorelaya. On the western side, between the Sviblova and Kolomenskaya towers, there were likely six towers that have not survived to this day. The Vodyaniye gates opened onto the Moscow River, near which was the Taynitskaya tower with an underground passage to the water. The Kosyye gates had an L-shaped passage and were located on the Kosaya Hill. The Melnichnye gates led to a mill on the opposite bank of the Kolomenka and had an over-gate tower, which was later dismantled. Between the Granovitaya and Kolomenskaya towers was the passage arch of the Malakhovskiye gates, built in the second half of the 16th century.

In August 1531, the construction of the kremlin was completed. Built in the style of the Moscow one, it was only slightly inferior to it. By the 17th century, when the borders of the state moved south, the fortress lost its defensive significance. In 1606, the city was captured by the troops of Ivan Bolotnikov, and during the Time of Troubles, it was repeatedly plundered by Polish-Swedish invaders. Nevertheless, Kolomna fully justified its purpose, becoming a symbol of the invulnerability of the Russian state. Steppe enemies were never able to capture this fortress in open battle, which served as a reliable shield for Moscow from the south.