Monoamine oxidases (MAO) are a valuable class of mitochondrial enzymes with a critical role in neuromodulation. In this study, we investigated the effect of natural MAO inhibitors on novel environment-induced anxiety by using the zebrafish novel tank test (NTT). Because zebrafish spend more time at the bottom of the tank when they are anxious, anxiolytic compounds increase the time zebrafish spend at the top of the tank and vice versa. Using this paradigm, we found that harmane, norharmane, and 1,2,3,4-tetrahydroisoquinoline (TIQ) induce anxiolytic-like effects in zebrafish, causing them to spend more time at the top of the test tank and less time at the bottom. 2,3,6-trimethyl-1,4-naphtoquinone (TMN) induced an interesting mix of both anxiolytic- and anxiogenic-like effects during the first and second halves of the test, respectively. TIQ was unique in having no observable effect on general movement. Similarly, a reference MAO inhibitor clorgyline—but not pargyline—increased the time spent at the top in a concentration-dependent manner. We also demonstrated that the brain bioavailability of these compounds are high based on the ex vivo bioavailability assay and in silico prediction models, which support the notion that the observed effects on anxiety-like behavior in zebrafish were most likely due to the direct effect of these compounds in the brain. This study is the first investigation to demonstrate the anxiolytic-like effects of MAO inhibitors on novel environment-induced anxiety in zebrafish.