Is it correct to use 首都 for capital of province? I am trying to do a cultural project on the city of Harbin. However, I'm not sure if it is correct to say this. I found out that Harbin was the capital of the province of Heilongjiang. If I said, 哈尔滨是黑龙江的首都, would it make sense since 首都 means capital.
No, you should use 省会 (provincial capital) instead, i.e. 哈尔滨是黑龙江的省会. You could also use 省城 (in a little old-style), or 首府 (especially for 自治区(autonomous region)).

首都 is only used for the capital of a country, e.g.北京是中国的首都.