Obec leží asi 6 km jižně od města Plumlov. Název obce je odvozen patrně od osobního jména Prostěj. Je proto docela možné, že město Prostějov a ves Prostějovičky měli společného zakladatele.

První zmínka o obci pravděpodobně pochází již z r.1131 v listině biskupa Zdíka. Tehdy ve vyjmenovaném majetku olomouckého kostela sv.Václava figuruje ves Prosteiouice-(Prostějovice). Samotný Prostějov byl jmenován Prosteiouicih tota. Prostějovičky se v nejstarší době nazývaly Prostějovice. Ještě r.1347 je uváděn tento název, dokonce se objevil na jedné z listin v r.1677. Tehdejší název vesnice způsobuje veliké problémy historikům. Mnohdy na některých listinách není jasné, zda se nejedná o dnešní Prostějov, který užíval v prvopočátku stejného názvu Prostějovice. První naprosto spolehlivá zpráva tak pochází až z r.1347, kdy bylo předáno plumlovské panství Benešovi II. z Kravař. V zemských deskách se vyskytuje jméno Prostějoviček r.1384, kdy Petr z Kravař vložil Erhartovi z Kunštátu panství plumlovské. V dalším období patřila vesnice drobné šlechtě. Majitelé se tak často střídali, až r.1527 se dostali zpět do plumlovského panství.