Mai-Mayevski nació en 1867 en el seno de una familia de la baja nobleza en la Gobernación de Maguilov, en la Bielorrusia moderna, por entonces parte del Imperio ruso. Comenzó su carrera militar en 1885; se graduó del Instituto de Ingeniería Nikoláievskoie (nombrado en honor al zar Nicolás I de Rusia) en 1888, luego asistió a la Universidad de Ingenieros Militares, y más tarde pasó a servir como teniente en el selecto Regimiento Izmáilovski. Luego asistió a la Academia Militar del Estado Mayor Nikoláievskaya en 1896, y ascendió a capitán de la unidad de guardias.
Cuando estalló la Revolución rusa de 1917, seguía al frente de 1.er Cuerpo de Guardias.[1] Pese a su aspecto obeso y poco marcial, era un militar de talento y gozaba de reputación de valiente, calmado y capaz de rápidas maniobras.[1][2]
Huyó a la región del Don en marzo de 1918 y se alistó en la fuerza «blanca» de Mijaíl Drozdovski como simple soldado. Esta pronto se unió al Ejército de Voluntarios, y a Mai-Mayevski se le dio el mando de una división, que acudió en auxilio de los cosacos del Don.[1] El 23 de mayo de 1919, se lo nombró jefe del Ejército de Voluntarios tras su brillante defensa del Dombás, en la que, pese a estar en notable inferioridad numérica, utilizó con habilidad la red ferroviaria de la región para defenderla;[1] en junio expulsó al Ejército Rojo de la ciudad de Járkov mediante la operación Járkiv.[2] Sus tropas saquearon la ciudad durante tres días con su consentimiento,[3] luego la usarían como cuartel principal.[4] En el avance hacia Moscú que ordenó Antón Denikin el 3 de julio, su ejército era el más occidental de los «blancos», y debía marchar hacia la capital enemiga siguiendo la ruta Kurks-Oriol-Tula-Moscú.[5][2] Sus fuerzas se apoderaron de Kiev,[6] Oriol[7] y Vorónezh entre agosto y finales de septiembre.[8] Sin embargo, estaban demasiado dispersas y sufrieron una serie de derrotas, que agudizaron el alcoholismo del general. Se lo culpó de la retirada de Tula y Oriol y se lo acusó de «corrupción moral» —era un alcohólico dado a las orgías y los burdeles y había ordenado pogromos—.[9] Había permitido, en efecto, el saqueo de las zonas conquistadas.[10] A principios de diciembre de 1919, el general Antón Denikin lo sustituyó por el general Piotr Wrangel,[6] un general eficaz sin las lacras morales de Mai-Mayevski.
En 1920, dirigió la retaguardia en la defensa final de Crimea. Hay diversas versiones sobre su muerte: una afirma que murió de un tiro durante la evacuación de Sebastopol el 13 de noviembre de 1920; otra, que falleció de infarto, bien en un hospital de Sebastopol, o en su coche cuando se dirigía a embarcarse para abandonar la ciudad.