If you really need to, you can say Maariv and Havdalah (omitting the blessing on the candle) from Plag HaMincha (1.25 hours before sunset) ([ShA OC 293:3][1]) just as much as you can say Maariv and Kiddush after that time on Friday. The blessing on the candle can be recited separately after nightfall. **All labor remains forbidden until after nightfall (even after saying Havdalah!).**

However, this should not be done ordinarily for it looks really weird (MA, Bach ibid.), there is a Mitzva to delay Havdalah in order to add on to Shabbat (ShA ibid. :1) (plus the leniency to daven Maariv early on Friday is even weaker without the advantage of adding on to Shabbat (Mishna Berura ibid. :9)), and people may come to perform forbidden labor before nightfall (ibid.).


  [1]: http://beta.hebrewbooks.org/tursa.aspx?a=oc_x1497