Safety of water was for a long time and still is one of the most pressing needs for many countries and different communities. Despite the fact that there are potentially many methods to evaluate water safety, finding a simple, rapid, versatile, and inexpensive method for detection of toxins in everyday items is still a great challenge. In this study, we extend the concept of composites, impregnated porous fibrous materials, such as fabrics and papers, by single-walled carbon nanotubes (SWNTs), toward very simple but high-performance biosensors. They utilize the strong dependence of electrical conductivity through nanotubes percolation network on the width of nanotube-nanotube tunneling gap and can potentially satisfy all the requirements outlined above for the routine toxin monitoring. An antibody to the microcystin-LR (MC-LR), one of the common culprits in mass poisonings, was dispersed together with SWNTs. This dispersion was used to dip-coat the paper rendering it conductive. The change in conductivity of the paper was used to sense the MC-LR in the water rapidly and accurately. The method has the linear detection range up to 10 nmol/L and nonlinear detection up to 40 nmol/L. The limit of detection was found to be 0.6 nmol/L (0.6 ng/mL), which satisfies the strictest World Health Organization standard for MC-LR content in drinking water (1 ng/mL) and is comparable to the detection limit of the traditional ELISA method of MC-LR detection, while drastically reducing the time of analysis by more than an order of magnitude, which is one of the major hurdles in practical applications. Similar technology of sensor preparation can also be used for a variety of other rapid environmental sensors.