Halkola liittyi [[Suomen Kommunistinen Puolue|Suomen kommunistiseen puolueeseen]] [[1973]]. Puolueen hajottua oppositiota kannattanut Halkola valittiin vuonna [[1986]] [[Demokraattinen vaihtoehtoVaihtoehto]] -puolueen puheenjohtajaksi, jossa tehtävässä hän toimi kolme vuotta. Hän oli samalla ensimmäinen naispuolinen puoluejohtaja Suomessa.<ref name=Apu1/> Deva sai [[Eduskuntavaalit 1987|vuoden 1987 eduskuntavaaleissa]] neljä kansanedustajaa, mutta puheenjohtaja jäi valitsematta.<ref>{{Verkkoviite|Osoite=http://yle.fi/elavaarkisto/?s=s&g=1&ag=4&t=295&a=2311|Nimeke=Vaalit 1987: Oikeisto ja vasemmisto liittoon|Julkaisu=YLE Elävä Arkisto| Ajankohta=30.10.2006| Viitattu=15.6.2010}}</ref> Halkola oli pitkään [[Helsingin kaupunginvaltuusto|Helsingin kaupunginvaltuutettu]].<ref>{{Verkkoviite|Osoite=http://www.suomalaisenelokuvanfestivaali.fi/site/index.php?option=com_content&task=view&id=47&Itemid=61|Nimeke=Suomalaisen elokuvan festivaali - Kristiina Halkola|Julkaisu=Suomalaisen elokuvan festivaali|Viitattu=15.6.2010}}</ref>
