I'd guess it's one of the non-Southern Slavic languages (e.g. Polish or Russian): those languages repurposed what used to be past participles (and so, just like adjectives, had genders) to be past tense verbs themselves. The Southern ones (e.g. Bulgarian) did not do this.
Yup, Polish.
Past tense in Russian also has gender. I was => был for the masculine case but to была for a female subject.