In the early 20th century gambling with dice was illegal in many states and so gamblers went to some pains to hide the dice when challenged by the police. Courts would sometimes throw out cases if the dice weren't offered in evidence. Thus "no dice." (source)
Today when we say it we are actually saying that we are refusing the proposal presented.