That depends on you. Just write first what comes natural to you. If you grab your guitar/play piano and you see that you can work your way in a harmony you like, start with that.
If you are thinking some lyrics without having any harmony, write them down.
There isn't any specific order in which to do that. Usually when I write a song, I first write the melody and then the harmony, but I have written songs the other way around.
So, just do things the way they come to you. You can do the other part after you've finished the first one and it'll be fine.
Αlso, another thing I have noticed, is that when I write the second part, I usually make changes to the first part I have written.