Par décret du Conseil des Ministres de juin 1954, des bureaux d'études spéciaux (SKB) sont créés dans les grandes usines automobiles pour développer du matériel militaire. Au MAZ, le SKB-1 est fondé le 23 juillet 1954 sous la direction de B. L. Shaposhnik, complété le 1er septembre par un atelier de production expérimentale fermé (TsOP). L'une de ses premières missions est la conception de deux tracteurs 8×8 pour l'artillerie : le MAZ-535 pour les systèmes de 10 t et le MAZ-536 pour ceux de 15 t. Le développement commence en septembre 1954. Le cahier des charges du ministère de la Défense impose une garde au sol d'un demi-mètre, le franchissement de gués de 1,3 m et de pentes de 30°, et un fonctionnement de -50 °C à +50 °C. Certaines sources voient dans son architecture, avec différentiels inter-ponts verrouillables et suspension indépendante sur toutes les roues, l'influence de l'automitrailleuse allemande capturée Büssing-NAG (Sd.Kfz. 234).

Les deux premiers prototypes sont assemblés en mai et juin 1956. Officiellement tracteur d'artillerie à ballast de 7 t de charge, il est prévu pour des pièces jusqu'à 10 t, dans des trains routiers allant jusqu'à 75,4 t. Premier véhicule militaire soviétique multi-essieux tout-terrain à transmission automatique, il pose les bases de la plupart des quatre-essieux lourds qui suivront. Il introduit d'un coup le convertisseur de couple, la transmission entièrement différentielle (sept différentiels, 16 arbres de transmission et huit réducteurs de moyeu planétaires), la suspension indépendante à barres de torsion sur toutes les roues, le gonflage centralisé des pneus et la direction assistée. Un pilote d'essai militaire résume la surprise : pas de pédale d'embrayage, pas de levier de vitesses, seulement l'accélérateur et le frein.

Il étrenne aussi le moteur de char D12A-375 de 39 l. Un préchauffeur issu des chars porte le liquide de refroidissement à 80 °C en 15 minutes par -40 °C, et le démarrage est doublé : démarreur électrique de 15 ch et bouteilles d'air comprimé à 150 atmosphères. Les premiers exemplaires ont trois pare-brise inclinés, un compartiment moteur plus bas à volets latéraux rabattables, et un phare central servant à l'éclairage infrarouge pour la vision nocturne, ce qui vaut à la famille le surnom de “Tsiklop” (Cyclope) dans l'armée.

Les essais révèlent une rigidité insuffisante du cadre. Le SKB conçoit un nouveau cadre en échelle riveté et soudé, à section en auge et longerons en Z inclinés, qui sera repris sur tous les multi-essieux de Minsk.

La version corrigée MAZ-535A apparaît en 1957 : cadre, caisse et ventilation du compartiment moteur renforcés, treuil de 15 tf. Elle se reconnaît à ses deux pare-brise et à son compartiment moteur rehaussé au niveau du toit de cabine, percé d'une double rangée de fentes verticales. Trois exemplaires sont éprouvés dans différentes zones climatiques à l'été 1957.

Elle est produite en petite série à Minsk à partir de 1958, puis transférée au KZKT de Kurgan, où le premier exemplaire sort en juin 1960 et la production continue jusqu'à fin 1964. Environ 200 exemplaires sont produits en 1961 et 150 en 1962. Les dernières séries, celles de Kurgan, perdent le phare central et gagnent de petits feux de position ronds sur les côtés de la cabine.

Présenté au public le 7 novembre 1961 sur la place Rouge, tractant un missile R-14 “Chusovaya”, il est adopté par l'Armée soviétique le 16 juillet 1962 et n'a servi que chez elle. Il tracte les canons M-47 de 152 mm et les remorques de transport des missiles R-5, R-12, R-14, R-16, R-26, R-36, GR-1 et RT-15, notamment sur les remorques 8T115 (R-12) et 8T139 (R-16). Il n'a jamais reçu d'armement. Côté civil, un convoi de trois 535A a transporté un transformateur de 200 t pour la centrale hydroélectrique d'Inguri.

Il est remplacé à partir de fin 1964 par le MAZ-537, dont la documentation est transmise au KZKT, et définitivement par le KZKT-537L comme tracteur à ballast.

Il est le tracteur d'artillerie de la famille 535/535B/535V, dont il est la base. Le MAZ-536 en est le frère plus puissant.