Nanocomposite carbon-paste electrodes (NC-CPEs) have been investigated for the first time in electrolyte-gated organic field-effect transistors (EGOFETs) as a replacement of conventional metal gate electrodes, using carbon nanotubes (CNTs) as a model carbon filler. Interestingly, the electrical properties of the resulting devices have been modulated by changing the loading percentage of CNTs within the insulating polymeric matrix. The potential of using such non-conventional gate electrodes for sensing purposes has also been evaluated by investigating, as a proof of concept, the formation of a supramolecular complex between a functionalized CNT-based NC-CPE containing β-cyclodextrin (β-CD) as a bio-recognition element and tryptophan (TRP). This approach, in synergism with the amplification function of an EGOFET, affords a shift in the threshold voltage (V) of the transistor, giving promising analytical results with detection limits at picomolar levels (1.0 ± 0.1 pM) as well as a linear response from 10 to 10 M. Accordingly, NC-CPEs have been demonstrated to be a potential alternative to metal gate electrodes for the development of a new generation of highly sensitive carbon-based EGOFET bio-sensors.