Alexander Alexeïevitch Rehbinder entstammt einer weitverzweigten deutsch-baltischen Familie. Sein Vater Alexei Maximowitsch Rehbinder [Алексей Максимович Ребиндер] (1795–1869) war russischer Generalleutnant und Unternehmer. Sein Großvater war Otto Friedrich von Rehbinder (* 1750) aus Livland, der mit Übertritt zum orthodoxen Glauben den Namen Maxim Karlowitsch Rehbinder (Максим Карлович Ребиндер) annahm.
Rehbinder war seit 1862 verheiratet mit Marija Nikolajewna Tolstaja (1838–1906), Tochter des Generals der Infanterie Nikolai Matwejewitsch Tolstoi (1802–1880) und Großenkelin von Fürst Kutusow. Die Kinder des Paares wurden zwischen 1918 und 1923 erschossen, lediglich Sohn Alexei (* 1865) emigrierte und starb 1932 in Deutschland.