Given the effect of a negative level, they would feel noticeably weakened. If it was dealt by a hidden method and they haven't experienced negative levels before, they may think it was a curse or disease instead, but they would know something was wrong.

Once they started getting close to death from negative levels (past halfway), I'd say there were even more notable effects - feeling like they might pass out at random times, sudden sensations of dread for no reason, darkness encroaching at the edge of their vision, etc.

Also, I'd think that the moment of taking a negative level would be painful, or at least highly unpleasant.