c. 1400, "pre-eminence, magnificence;" early 15c., "greatness of size or extent," from Latin magnitudo "greatness, bulk, size," from magnus "great" (from suffixed form of PIE root *meg- "great") + -tudo, suffix forming abstract nouns from adjectives and participles (see -tude).
Meaning "size, extent," whether great or small is from early 15c. Of stars, "brightness or brilliancy expressed as a number" (now on a logarithmic scale) from 1640s, translating Ptolemy's Greek megethos.